Hi Folks,

I've written a macro which produces the 3d convex hull of an arbitrary 
point cloud using a 'beneath-beyond' type algorithm.

It grew out of a simple wish to triangulate the surface of a sphere for 
use in a mechanics simulation. My first few attempts failed rather too 
easily, so I read up on the problem and this came out of it.

It can get a bit slow - 500 co-spherical points takes about three and a 
half minutes to parse on my 1GHz Athlon - and it probably scales at 
something between O(n^2) and O(n^3) with the worst case being all points 
on the hull.

The two images are:

200 co-spherical points giving a hull of all points, 594 edges and 396 
triangles;

400 points from VRand_In_Box() giving a hull of 55 points, 159 edges and 
106 triangles.

I'll post the files to p.b.s-f in a moment. Please let me know if anyone 
finds them useful ...

Bye for now,
	Mike Andrews.

Post a reply to this message

Attachments:
Download 'convhull3.jpg' (31 KB) Download 'convhull5.jpg' (26 KB)

Preview of image 'convhull3.jpg'

Preview of image 'convhull5.jpg'